package 动态规划.背包And分组And切割问题系列;

import org.junit.Test;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/16 7:40
 */
public class lc2478完美分割的方案数 {


    static final int MOD = 1000000007;


    /*
     O(N ^ 3)
     一个算法， N 的取值范围是 1000， 这肯定过不了的！
     */
    public int recursion(int index,int k,int minLength,String s){
        if(index == s.length()){ // 这种是 分组， 是必须， 走到 字符串的 末尾 的！ ， 所以这个basecase 才是 最合理的basecase
            return k == 0 ? 1 : 0;
        }
//        if(!judge(s.charAt(index))){
//            return 0;
//        }
        long ans = 0;
        // 直接 从minLength 开始进行枚举就行了！  //如果当前index 就不是 质数， 就不用走了， 直接返回
        for(int i = index + minLength;i <= s.length() && judge(s.charAt(index));i++){
           if(!judge(s.charAt(i - 1))){
               ans += recursion(i,k - 1,minLength,s);
           }
           ans %= MOD;
        }
        return (int)ans;
    }

    // 判断是不是质数数字
    public boolean judge(Character ch){
        if("2357".indexOf(ch) != -1){
            return true;
        }
        return false;
    }

    public int dp(String s,int k,int minLength){
        int len = s.length();
        int dp[][] = new int[len + 1][k + 1];
        dp[len][0] = 1;
        for(int index = len - 1;index >= 0;index--){
            if(!judge(s.charAt(index))){
                continue;
            }
            /*
             曹： 不要用 太过相近的 变量名称， 比如这里的 k1 和 k ， 最后写的时候可能会分不清， 你写的是k1 还是k
             */
            for(int k1 = 1;k1 <= k;k1++){
                long ans = 0;
                for(int i = index + minLength;i <= len && judge(s.charAt(index));i++){
                    if(!judge(s.charAt(i - 1))){
                        ans += dp[i][k1 - 1];  // 一看到这种， 就去想，会不会有越界的存在！
                    }
                }
                dp[index][k1] = (int)(ans % MOD);
            }
        }
        return dp[0][k];
    }

    public int dpFinal(String s,int k,int minLength){
        int len = s.length();
        int dp[][] = new int[len + 1][k + 1];
        dp[len][0] = 1;
        for(int index = len - 1;index >= 0;index--){
            if(!judge(s.charAt(index))){
                continue;
            }
            /*
             曹： 不要用 太过相近的 变量名称， 比如这里的 k1 和 k ， 最后写的时候可能会分不清， 你写的是k1 还是k
             */
            for(int k1 = 1;k1 <= k;k1++){
                long ans = 0;
                dp[index][k1] = !judge(s.charAt(index + minLength - 1)) ? dp[index + minLength][k1 - 1] + dp[index + 1][k1] : dp[index + 1][k];
                dp[index][k1] = (int)(ans % MOD);
            }
        }
        return dp[0][k];
    }

















    @Test
    public void test(){
        String s = "23542185131";
        int k = 3;
        int len = 2;
        System.out.println(dp(s,k,len));
        System.out.println(dpFinal(s,k,len));
    }



}
